1. Field of the Invention
The present invention relates generally to improved terrain mapping in interactive 3D computer graphics applications.
2. Description of the Related Art
Flight simulation is the quintessential example of interactive 3D computer graphics applications. The purpose of any flight simulator Image Generator (IG) is to provide one or more pilots with a virtual representation of the real world (especially outside the cockpit) to the maximum degree of fidelity possible with available technology. The more realistic the rendering is, the more effective the training. Since the earliest days of 3D flight simulators, there has been some representation of the terrain (i.e. the ground, lakes, rivers, ocean, etc.). At first, this was just a simple horizon dividing a blue sky from green earth, providing not even the illusion of traveling over the earth. Later came systems using xe2x80x9cgeotypicalxe2x80x9d terrain, in which swatches of real-looking terrain were stitched together to provide the illusion of flying over an actual place (e.g. landscapes similar to what one might see in the vicinity of Darmstadt, Germany). These systems generally use actual elevation data from the region being simulated, but generic texture maps. For example, the locations of farmland, desert, and cities might be consistent with reality, while the images used to represent these types of terrain do not correspond to the actual farms and cities over which flight is being simulated.
The current state of the art is known as geospecific terrain, in which both the elevation data and the texture maps that are combined to form the terrain are derived from the real world. The elevation data is typically obtained using radar from satellites (e.g., DTED-1, DTED-2), or other conventional imaging systems. The texture data is also typically obtained from satellite imagery, although aerial photography is commonly used as well. The quality of both elevation and texture data is measured in terms of its resolution. For elevation, this means the distance between xe2x80x9cpostings,xe2x80x9d meaning the locations where the height of the earth is sampled. For example, DTED-1 elevation data provides elevation at roughly 90-meter postings. Imagery resolution is measured similarly. For example, in 16-meter imagery, a single texel (texture element) corresponds to a 16 mxc3x9716 m square of the ground. Imagery is available in much higher resolutions, such as 20 cm and beyond.
Additionally, flight simulation is no longer limited to the visual spectrum. For military flight simulators, it is important to also simulate sensors, such as FLIR (Forward Looking Infra Red), NVG (Night Vision Goggles), low light level television, and Radar. In a geospecific simulator, multispectral or hyperspectral (i.e. some or many wavelengths) imagery may be used in conjunction with an accurate model of the sensor""s spectral response characteristics to create a physics-based simulation of how a particular sensor will behave during a simulated mission.
For any flight simulator, whether geospecific or geotypical, the distance to the horizon is an important factor in realism. Some simulators have very short horizons, e.g., 5 nautical miles (nmi), which causes the experience to be like constantly flying through dense fog, regardless of the simulated weather conditions. For jet simulators, a horizon of 50 nmi is generally acceptable, and for helicopters, 30 nmi is generally acceptable for effective training using commercially available flight simulators consistent with the current state of the art. In the real world, however, horizons can be much farther, reaching as far as 100 nmi for turbine aircraft. Keeping a large horizon range while showing realistic close range detail at real time interactive update rates is one significant challenge faced by designers of terrain rendering algorithms.
Transforming raw source data into a visual simulation that a user can experience typically involves two main steps: Database Creation and Interactive Rendering. The scene database is a collection of all the data fed into the IG to produce a realistic simulation of a particular place, and particular tactical data (such as specific enemy planes, tanks, etc.), in a format that the image generator can understand and efficiently render. While there are several common, or xe2x80x9copenxe2x80x9d database formats, it is often necessary to translate these databases into proprietary formats that are optimized for the technical characteristics of a specific IG. Terrain is the largest element of a large geospecific database. The texture and elevation data can range in size from a few gigabytes to over a terabyte for a single scene database. Since the early days of image generation, the position of the pilot""s viewpoint (also known as the xe2x80x9cownshipxe2x80x9d) has been used to control reading, or xe2x80x9cpagingxe2x80x9d of data from an input/output device such as a disk storage system or network. This is especially important for large scene databases because it is impractical or impossible to store the entire scene database in high-speed memory such as RAM.
For geospecific terrains, the Database Creation process includes orthorectification of elevation and imagery, creating 3D geometry from elevation data, assembling individual images into larger texture maps, and converting these texture maps into a format usable by the IG. Generally, the amount of data decreases during this process, as elevation is subsampled to match the geometry performance of the IG and the imagery""s precision (the number of bits used to represent each texel) is reduced to match bandwidth constraints of the IG. Multiple Levels of Detail (LOD) of the elevation geometry are generally created, and texture MIP levels are also created.
The Interactive Rendering process is where the IG must render the xe2x80x9carea of regardxe2x80x9d of the pilot (i.e. the pilot""s current surrounding environs) at a rate equal to the display""s refresh rate, typically 60 Hz. It is important that the IG constantly meet this refresh rate target, or the scene will appear to stutter or jitter, which is unacceptable for effectively training pilots. The 3D scene can comprise many elements, including sky, sun, clouds, terrain (including ocean), air targets (i.e., other aircraft), ground targets (e.g., tanks, trucks), special effects (e.g., explosions, smoke columns), and cultural features (e.g., buildings, trees). Some of these elements (targets, terrain, cultural features) are contained in the scene database. Other elements (such as special effects, sea) are generated procedurally within the Image Generator.
The method used for rendering the terrain depends on how the data is organized in the scene database. Most geospecific flight simulators organize the terrain geometry into xe2x80x9ccells.xe2x80x9d In Aechelon Technology""s C-Nova Image Generator, for example, which is a runtime engine for flight training applications that transforms commercially available platforms into high-resolution, multi-spectral, multi-channel, geo-specific image generators, the terrain is subdivided into 5 km square cells. For a 1000 kmxc3x971000 km database, there are 40,000 cells. The structure is similar to a quilt, where each cell is a xe2x80x9csquare.xe2x80x9d The pilot flies over the quilt. Generally, each cell can be rendered at multiple LODs, with the finest levels of detail drawn nearest the viewer (xe2x80x9cownshipxe2x80x9d) and the coarsest LODs drawn at the horizon. One purpose for using a LOD mechanism is to maximize the finite geometry capability of the graphics subsystem. It is not necessary to render fine LODs far from the viewer because the fine and coarse LODs are essentially indistinguishable at that range: Beyond a certain range, the cells are not drawn at all. Modern IGs perform xe2x80x9cview frustum culling,xe2x80x9d in which objects (including terrain cells) that fall entirely outside the viewport (display) are excluded from rendering at the per-object or greater level. In some systems, terrain cells are merged into larger cells in the coarser LODs. This technique can be desirable because it allows a greater variance in the number of polygons per square kilometer along the LOD continuum.
Some IGs have support for fading between LODs, in which a cell in transition between two levels of detail undergoes a blending operation to cause the new LOD to fade in and the old LOD to fade out. This is a desirable form of LOD transitions, because instant transitions and geometry morphing schemes are easily noticed, and cause distractions objectionable to pilots, but it involves a negative impact on performance, since both the coarse and detailed objects are drawn and blended during the transition. It is important to preserve the xe2x80x9csuspension of disbeliefxe2x80x9d during the entirety of a simulation. LOD fading is a difficult feature to attain without specialized hardware because of ordering considerations when using alpha blending. Those skilled in the art are aware that the most widely available realtime transparency algorithms are order-dependent, where partially transparent objects must be drawn after the objects they occlude. Hardware such as the SGI InfiniteReality graphics engine provides a multisample alpha (MSAlpha) mechanism for order-independent transparency. While this eliminates the need for computationally expensive sorting, it is a costly xe2x80x9chigh-endxe2x80x9d graphics system, and therefore not an adequate solution for most end users.
Non-cellular terrains also exist in the prior art. Most of the non-cellular approaches use a technique called xe2x80x9cdynamic terrain,xe2x80x9d in which the Image Generator regenerates a polygon mesh for each particular viewpoint or set of similar viewpoints, with either a continuous triangulation topology such as Delaunay triangulation (used in the Silicon Graphics Advanced Surface Definition (ASD) terrain implementation) or a dynamic meshing scheme such as the Evans and Sutherland xe2x80x9cmorphing terrainxe2x80x9d described by Michael Cosman in his 1992 Image Conference paper, where the terrain elevation data is meshed in real time with an irregular hierarchical polygon grid.
For large-area geospecific databases, which use large quantities of satellite imagery and/or aerial photography, the size of the terrain texture vastly exceeds the amount of texture memory available in the graphics subsystem. For this reason, a xe2x80x9cpagingxe2x80x9d system is commonly employed. The paging system uses a pool of texture memory for the area of regard, and updates the edges of the texture memory as the pilot flies across the scene database. OpenGL provides a mechanism called glTexSubImage to allow an application to update a subset of a texture map in memory. An alternative to a texture paging scheme such as this is to divide the texture into cells aligned with the terrain cells, and apply each individual texture map to its corresponding terrain cell. However, this method requires a surprisingly large amount of texture memory and state-change overhead and is not in wide use.
Specialized hardware can also assist with the challenge of applying the texture map to the terrain geometry. For example, SGI""s InfiniteReality graphics engine provides a specialized mechanism called xe2x80x9cClip-Map,xe2x80x9d which, enabled through SGI""s IRISPerformer API, provides a xe2x80x9cvirtual MIP-mapxe2x80x9d that handles texture paging transparent to the application and allows the texture map organization to be totally decoupled from the terrain geometry structure. Clip-mapping also transparently allows a terrain texture to be sparsely populated, meaning the overall terrain texture map can have varying resolutions at different areas. Other products such as Evans and Sutherland""s ESIG 4000 also provide support for sparse population of terrain texture. In a traditional MIP-map, a base texture of some size (e.g., 1024xc3x971024 texels) is decimated into xe2x80x9cMIP levels,xe2x80x9d each xc2xd the size of the finer level (e.g., 512xc3x97512, 256xc3x97256, . . . ,1xc3x971). The purpose of pre-filtering the texture map into levels is to allow for efficient rendering of textured objects at any range or orientation with consistent quality. Without the ability to sparsely populate a terrain texture, the amount of disk space required to store the texture would be much larger than necessary. For example, suppose a 1000 kmxc3x971000 km database with a base resolution of 16 m per texel, with a single airfield where 1 m per texel imagery is required over a 10 kmxc3x9710 km area. With sparsely populated texture, the database might require 1 GB for the entire texture. With a conventional MIP-map, the size of the texture map would be 1.3 TB. This is because the 16 m level would need to be supersampled up to 1 m over the entire database. Because of this effect, storing the terrain texture in the database in a sparsely-populated form is very desirable.
Accordingly, no terrain schemes are known that are simultaneously geospecific, capable of covering large areas, and feature LOD fading without the use of costly, special-purpose hardware. Additionally, no terrain schemes are known that are capable of rendering both high detail in the foreground and physically realistic horizons at high altitudes while meeting the requirements of geospecificity and LOD fading. Therefore, the problem of interactively rendering terrain has not yet been adequately solved. A terrain rendering method is needed that is as or more realistic than that which is currently available in the art, and which can be implemented on commodity hardware not possessing special-purpose high-end features.
In accordance with the present invention, there is provided a system and method for interactive rendering of geospecific terrain. The present invention requires no special-purpose hardware and enables a highly realistic experience by providing high foreground detail, far horizons and minimized LOD transition artifacts through LOD fading. The resulting visual experience exceeds the realism of previous methods without compromising strict interactive performance requirements.
The present invention solves the terrain rendering problem by constructing a number of fixed terrain layers centered about the viewer, in a configuration such that each layer resembles a xe2x80x9cmagic carpetxe2x80x9d on which the viewer (ownship) flies. Each concentric layer covers a successively larger area of the visual database, and the vertex density and texture resolution of each layer is independent of other layers. Furthermore, each layer may feature a fading band around its circumference that facilitates fading between consecutive LODs (layers). This approach achieves optimal vertex density/range distribution, which enables both very far horizons (exceeding 100 nmi) and very high elevation detail in the foreground, while maintaining strict performance requirements. High texture resolution (less than 0.5 m) and sparsely populated terrain texture are also achieved without the use of specialized hardware because each layer is textured independently. Thus, the present invention overcomes the need for special-purpose hardware and provides a superior visual experience compared to previously available techniques.
One goal of most geospecific terrain rendering systems is to provide the pilot with the most realistic experience possible without compromising the strict update rate requirementxe2x80x94typically 60 Hz. Within this constraint, realism is enhanced by maximizing the resolution of terrain geometry and texture near the viewer. The use of both multiple geometrical LODs and texture MIP levels is desirable to meet quality and performance criteria. It is important, therefore, to provide a mechanism for fading between geometry LODs and for rendering a sparsely populated terrain texture.
In the present invention, the terrain is organized into a finite number of layers, which are centered about the viewer, wherein the first layer is of a specific size (e.g., 5 km) and each subsequent layer is some multiple, e.g., twice, two-and-a-half, etc., as large as its predecessor. The vertex density of each layer is independent of the other layers, typically with the highest vertex density in the smallest layer and the progressively lower vertex densities in the larger layers. Each layer preferably includes a fade band around its circumference, which facilitates the fading between consecutive layers.
Each layer may be subdivided into sectors to facilitate culling. In one embodiment, nine sectors are used to allow a simple configuration having a center sector that corresponds to where layers overlap. For layers covered by smaller layers, the center sector may not be rendered, resulting in reduced scene complexity. The layers are drawn in order from the largest to the smallest to facilitate the LOD fading. In order to prevent the layers from interpenetrating, the layers are drawn without depth testing. Consequently, the individual primitives comprising the layers are preferably sorted from back-to-front in a manner similar to the Painter""s Algorithm, which is conventionally known.
Each layer is rendered with one or more texture maps bound to the layer, which is populated with data from the overall terrain texture using a conventional texture paging mechanism. The sizes of the texture maps are independent, although for a given layer size, the texture is preferably sized such that the valid area of the texture (each texture has a paging band around its edges into which texture paging subloads occur) maps to the layer size with a ratio available in the overall terrain texture. For example, if the terrain texture contains levels that are multiples of 1.1 meters per texel, a texture with a valid area of size 960 texels will map to a layer whose size is a multiple of 1056 meters.
In the scene database, the terrain elevation is also organized into layers, with one terrain elevation layer per rendering layer. Each terrain layer in the database is subdivided into equally sized tiles, each the size of the rendering layer. A tile is preferably comprised of Nxc3x97N vertices, organized topologically into rows and columns, as well as metadata such as the minimum and maximum height of the tile, the terrain type for the tile, etc. The texture map in the database is also arranged into tiles, which are of uniform, but arbitrary size. However, texture levels that are smaller than the tile size may be stored in their correct size. Texture data is stored in a Sparse Image Pyramid, wherein the finest resolution for a given area is arbitrary (constrained to tile and level boundaries). For any given finest resolution, a complete set of decimated levels of the texture are present in the pyramid.
Sea is also supported using this terrain rendering approach, through a set of sea rendering layers corresponding to some or all of the terrain rendering layers. The sea rendering layers are subdivided into sectors in a manner similar to the terrain rendering layers. A tile type field contained in the terrain layers in the database is preferably sampled per-sector to activate or deactivate the sectors of each layer in the terrain rendering layers and the sea rendering layers. A per-texel transparency component stored in the terrain texture pyramid allows fine definition of coastlines.